import java.util.ArrayList;

/**
 * 300.最长递增子序列
 */
public class Exerciser5 {
    // 在考虑最长的子序列的时候呢，不会去考虑子序列中的数据，只会关系子序列的长度
    // 仅需要关系子序列的最后一个位置的数据是谁
    public int lengthOfLIS(int[] nums) {
        // 贪：
        // 存什么：所有长度为 x 的递增子序列中，最后一个元素的最小值 (也就是把每一个长度中的数据都放置为最小值)
        // 存哪里：所有大于等于 nums[i] 的最小值的位置 (也就是把要存在数据存放到大于等于这个nums[i]值的第一个位置)
        // 10,9,2,5,3,7,101,18
        // 长度1：/10 9(9小于10放不到10后面，可以替代10，因为可以放到10后的也可以放到9后，替换之后，把10去掉)/ 2(和9的原理一致)
        // 长度2：5(比长度为1时的数据2大，放到2后，也就是长度为2的数据)  （之后的数据也是按照同样的规则）

        // 放到数组中后，数据是严格递增的，所以在 存哪里 的时候呢可以使用 二分 进行优化查找
        ArrayList<Integer> ret =  new ArrayList<>();
        int n = nums.length;
        ret.add(nums[0]);

        for(int i = 1;i < n;i++) {
            if(nums[i] > ret.get(ret.size() - 1)) {
                // 说明新的数据比 数组中的最后面的值的，可以放到其后面，直接存放
                ret.add(nums[i]);
            }else {
                // 小于等于的话，直接在数组中进行查找 存哪里 这个操作
                int left = 0,right = ret.size() - 1;
                while(left < right) {
                    int mid = (left + right) / 2;
                    if(ret.get(mid) < nums[i]) {
                        left = mid + 1;
                    }else {
                        right = mid;
                    }
                }
                // 更新left位置的数组中的数据
                ret.set(left,nums[i]);
            }
        }
        return ret.size();

    }
}
